﻿#ifndef __INSERTION__
#define __INSERTION__
//适应性排序算法
//O（n*n）
template <class item>
void insertion(item arr[], int left, int right){
	if(arr == NULL || right == left) return ;
	assert(right > left);
	for(int i = left + 1; i <= right; ++i){
		item key = arr[i];
		int j = i-1;
		for(;;){
			if(j < left || key >= arr[j]) break;
			arr[j+1] = arr[j--];
		}
		arr[j+1] = key;
	}
}
//首先将最小值放置数组首位(可以放哨兵，也可遍历寻找最小值)
//改善的细节在于循环内部不需要每次判断边界
template <class item>
void insertion_improved(item arr[], int left, int right){
	if(arr == NULL || right == left) return ;
	assert(right > left);
	int min = left;
	for(int i = left + 1; i <= right; ++i)
		if(arr[min] > arr[i]) min = i;
	exchange(arr[min], arr[left]);
	for(int i = left+2; i <= right; ++i){
		item key = arr[i];
		int j = i-1;
		for(;;){
			if(key >= arr[j]) break;
			arr[j+1] = arr[j--];
		}
		arr[j+1] = key;
	}
}
#endif